﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GISCore.Geometry.Partition
{
    public class PolygonReconstuctor:IReconstuctionable
    {

        private double _xmin;
        private double _xmax;
        private double _ymin;
        private double _ymax;
        private GridIntersectPoint _leftBottomPoint = null;
        private GridIntersectPoint _rightBottomPoint = null;
        private GridIntersectPoint _leftTopPoint = null;
        private GridIntersectPoint _rightTopPoint = null;
        private List<GridIntersectPoint> _topGridIntersectPoints;
        private List<GridIntersectPoint> _bottomGridIntersectPoints;
        private List<GridIntersectPoint> _leftGridIntersectPoints;
        private List<GridIntersectPoint> _rightGridIntersectPoints;

        private List<IntersectPoint> intersectPoints;

        private List<LinkedPoint> _topMergingIntersectPoints = null;
        private List<LinkedPoint> _bottomMergingIntersectPoints = null;
        private List<LinkedPoint> _leftMergingIntersectPoints = null;
        private List<LinkedPoint> _rightMergingIntersectPoints = null;

        // Each polygon has a set of points, and there are a set of polygons in the cell
        List<PostPolygon> _postPolys = null;
        //the set of the polygons within the range 
        HashSet<Polygon> set = new HashSet<Polygon>();

        public void clear()
        {
            
            _topMergingIntersectPoints = new List<LinkedPoint>();
            _bottomMergingIntersectPoints = new List<LinkedPoint>();
            _leftMergingIntersectPoints = new List<LinkedPoint>();
            _rightMergingIntersectPoints = new List<LinkedPoint>();
            set.Clear();
            _postPolys = new List<PostPolygon>();
        }
        public IEnumerable<PostPolygon> reconstruct(IEnumerable<Line> lines, ICellable cell,
           double xmin, double xmax, double ymin, double ymax)
        {
            IEnumerable<LinkedPoint> uptemp = null;
            IEnumerable<LinkedPoint> downtemp = null;
            IEnumerable<LinkedPoint> lefttemp = null;
            IEnumerable<LinkedPoint> righttemp = null;
            var p= reconstruct(lines, cell.getIntersectPoint(), cell.getTopGridIntersectPoint(),
                                cell.getBottomGridIntersectPoint(), cell.getLeftGridIntersectPoint(),
                                cell.getRightGridIntersectPoint(), out uptemp, out downtemp, out lefttemp, out righttemp,xmin, xmax, ymin, ymax);

            (cell as Cell)._upLinkedPoints = uptemp as List<LinkedPoint>;
            (cell as Cell)._downLinkedPoints = downtemp as List<LinkedPoint>;
            (cell as Cell)._leftLinkedPoints = lefttemp as List<LinkedPoint>;
            (cell as Cell)._rightLinkedPoints = righttemp as List<LinkedPoint>;
            return p;
        }

        public IEnumerable<PostPolygon> reconstruct(IEnumerable<Line> lines, IEnumerable<IntersectPoint> intersectPoints, IEnumerable<GridIntersectPoint> topGridIntersectPoints, IEnumerable<GridIntersectPoint> bottomGridIntersectPoints, IEnumerable<GridIntersectPoint> leftGridIntersectPoints, IEnumerable<GridIntersectPoint> rightGridIntersectPoints, out IEnumerable<LinkedPoint> topMergingIntersectPoints, out IEnumerable<LinkedPoint> bottomMergingIntersectPoints, out IEnumerable<LinkedPoint> leftMergingIntersectPoints, out IEnumerable<LinkedPoint> rightMergingIntersectPoints, double xmin, double xmax, double ymin, double ymax)
        {
            clear();
            this._xmin = xmin;
            this._xmax = xmax;
            this._ymin = ymin;
            this._ymax = ymax;
            this.intersectPoints = intersectPoints as List<IntersectPoint>;
            _leftBottomPoint = new GridIntersectPoint(xmin,ymin);
            _rightBottomPoint = new GridIntersectPoint(xmax, ymin);
            _leftTopPoint = new GridIntersectPoint(xmin,ymax);
            _rightTopPoint = new GridIntersectPoint(xmax,ymax);
            this._topGridIntersectPoints = (List<GridIntersectPoint>)topGridIntersectPoints;
            foreach (var p in _topGridIntersectPoints)
            {
                p.setLinkedPoint(null);
            }
            this._bottomGridIntersectPoints = (List<GridIntersectPoint>)bottomGridIntersectPoints;
            foreach (var p in _bottomGridIntersectPoints)
            {
                p.setLinkedPoint(null);
            }
            this._leftGridIntersectPoints = (List<GridIntersectPoint>)leftGridIntersectPoints;
            foreach (var p in _leftGridIntersectPoints)
            {
                p.setLinkedPoint(null);
            }
            this._rightGridIntersectPoints = (List<GridIntersectPoint>)rightGridIntersectPoints;
            foreach (var p in _rightGridIntersectPoints)
            {
                p.setLinkedPoint(null);
            }
            _identifyPolygons(lines);
            this._postPolys=intersect(intersectPoints as List<IntersectPoint>);
            topMergingIntersectPoints = this._topMergingIntersectPoints;
            bottomMergingIntersectPoints = this._bottomMergingIntersectPoints;
            leftMergingIntersectPoints = this._leftMergingIntersectPoints;
            rightMergingIntersectPoints = this._rightMergingIntersectPoints;
            return this._postPolys;
        }
        /// <summary>
        /// identify polygons within the range
        /// </summary>
        private void _identifyPolygons(IEnumerable<Line> lines)
        {

            Polygon poly;
            foreach (Line l in lines)
            {
                if (l.parent == null)
                {
                    poly = l.getPolygon();
                }
                else
                {
                    poly = l.parent.polygon;
                }

                if (set.Add(poly))
                {
                    /* for each polygon within the range, identify the points in the range*/
                    this._postPolys.Add(this._getPartialPoint(poly));
                }
            }
        }

        /// <summary>
        /// configure the incoming and outcoming postPolygon for each intersect point.
        /// </summary>
        /// <param name="next"></param>
        /// <param name="pre"></param>
        /// <param name="poly"></param>
        /// <param name="itsLine"></param>
        /// <param name="otherLine"></param>

        private void _configureIntersectPoint(LinkedPoint next, LinkedPoint pre, Polygon otherPoly, Line itsLine, Line otherLine, ref LinkedPoint headIntersectPoint, ref LinkedPoint currentIntersectPoint)
        {
            Point nextPoint=next.getPoint();
            Point prePoint=pre.getPoint();
            if (otherPoly.enterPolygon(nextPoint, prePoint, otherLine))
            {
                ((IntersectPoint)nextPoint).inComing = next;
                ((IntersectPoint)nextPoint).inComingLine= itsLine;
                ((IntersectPoint)nextPoint).outGoingLine = otherLine;
                if (currentIntersectPoint != null)
                {
                    headIntersectPoint = next;
                    ((IntersectPoint)(currentIntersectPoint.getPoint())).inNext = next;
                    currentIntersectPoint = next;
                }
                else
                {
                    currentIntersectPoint = next;
                }
            }
            else
            {
                ((IntersectPoint)nextPoint).outGoing = next;
                ((IntersectPoint)nextPoint).outGoingLine = itsLine;
                ((IntersectPoint)nextPoint).inComingLine = otherLine;
                if (currentIntersectPoint != null)
                {
                    headIntersectPoint = next;
                    ((IntersectPoint)(currentIntersectPoint.getPoint())).outNext = next;
                    currentIntersectPoint = next;
                }
                else
                {
                    currentIntersectPoint = next;
                }
            }
        }
        
        /// <summary>
        /// Retrieve a set of points in a polygon that are within the range
        /// For intersect points, we also specify its incoming line nad outcoming line.
        /// </summary>
        /// <param name="poly"></param>
        /// <returns></returns>
        private PostPolygon _getPartialPoint(Polygon poly)
        {
            List<Point> poly_points = poly.getPoints();
            PostPolygon postPoly = new PostPolygon();
            LinkedPoint current = null;
            LinkedPoint otherPoint;
            LinkedPoint specialPoint=null;
            LinkedPoint currentIntersectPoint = null;
            LinkedPoint tempLinkedPoint = null;
            LinkedPoint headIntersectPoint = null;
            GridIntersectPoint endpoint = null;
            Polygon otherPoly;
            Line itsLine,otherLine;
            VirtualIntersectPoint currentVIP;
            VirtualIntersectPoint otherVIP;

            foreach (Point p in poly_points)
            {
                // if the point is in the cell
                if (_withinRange(p))
                {
                    tempLinkedPoint = new LinkedPoint(p);
                    if (postPoly.getHead() == null)
                    {
                        postPoly.setHead(tempLinkedPoint);
                        postPoly.setPolygon(poly);
                        current = tempLinkedPoint;
                        tempLinkedPoint.setPostPolygon(postPoly);
                        continue;
                    }
                    else
                    {
                        tempLinkedPoint.setPre(current);
                        current.setNext(tempLinkedPoint);
                        tempLinkedPoint.setPre(current);
                        current = tempLinkedPoint;
                        tempLinkedPoint.setPostPolygon(postPoly);
                    }
                    if (p is IntersectPoint)
                    {
                        if (((IntersectPoint)p).inComingLine.polygon == poly)
                        {
                            otherLine = ((IntersectPoint)p).outGoingLine;
                            otherPoly = otherLine.polygon;
                            itsLine = ((IntersectPoint)p).inComingLine;
                        }
                        else
                        {
                            otherLine = ((IntersectPoint)p).inComingLine;
                            otherPoly = otherLine.polygon;
                            itsLine = ((IntersectPoint)p).outGoingLine;
                        }
                        //configure the intersect point.
                        _configureIntersectPoint(current, current.getPre(), otherPoly, itsLine, otherLine, ref headIntersectPoint,ref currentIntersectPoint);
                    }
                }
                // if the point is on the border of the cell
                else if (_onBorder(p))
                {
                    // if it is the first point
                    if (postPoly.getHead() == null)
                    {
                        if (((GridIntersectPoint)(p)).getLinkedPoint() != null)
                        {
                            otherPoint = ((GridIntersectPoint)(p)).getLinkedPoint();
                            tempLinkedPoint = new LinkedPoint(otherPoint.getPoint());
                            tempLinkedPoint.setPostPolygon(postPoly);
                            ((VirtualIntersectPoint)(tempLinkedPoint.getPoint())).inComing = tempLinkedPoint;
                            Line tempLine = Line.generateDummyLine();
                            tempLine.setPolygon(poly);
                            ((VirtualIntersectPoint)(tempLinkedPoint.getPoint())).inComingLine = tempLine;
                        }
                        else
                        {
                            tempLinkedPoint = new LinkedPoint(p);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            tempLinkedPoint.setPre(current);
                            ((GridIntersectPoint)(p)).setLinkedPoint(tempLinkedPoint);
                        }
                        postPoly.setHead(tempLinkedPoint);
                        postPoly.setPolygon(poly);
                        current = tempLinkedPoint;
                        continue;
                    }
                    if (_onBorder(current.getPoint()))
                    {
                        double x1 = current.getPoint().getX();
                        double y1 = current.getPoint().getY();
                        double x2 = p.getX();
                        double y2 = p.getY();

                        endpoint = null;
                        if ((x1 == _xmin) && (y2 == _ymin))
                        {
                            endpoint = this._leftBottomPoint;
                        }
                        else if ((y1 == _ymin) && (x2 == _xmax))
                        {
                            endpoint = this._rightBottomPoint;
                        }
                        else if ((x1 == _xmax) && (y2 == _ymax))
                        {
                            endpoint = this._rightTopPoint;
                        }
                        else if ((y1 == _ymax) && (x2 == _xmin))
                        {
                            endpoint = this._leftTopPoint;
                        }
                        else if ((x1 == _xmin) && (y2 == _ymax))
                        {
                            endpoint = this._leftTopPoint;
                        }
                        else if ((y1 == _ymax) && (x2 == _xmax))
                        {
                            endpoint = this._rightTopPoint;
                        }
                        else if ((x1 == _xmax) && (y2 == _ymin))
                        {
                            endpoint = this._rightBottomPoint;
                        }
                        else if ((y1 == _ymin) && (x2 == _xmin))
                        {
                            endpoint = this._leftBottomPoint;
                        }

                        if (((GridIntersectPoint)(p)).getLinkedPoint() != null)
                        {
                            // configure intersect points;
                            //currentVIP = new VirtualIntersectPoint(p.getX(), p.getY());
                            otherPoint = ((GridIntersectPoint)(p)).getLinkedPoint();
                            currentVIP = otherPoint.getPoint() as VirtualIntersectPoint;
                            //intersectPoints.Add(currentVIP);
                            tempLinkedPoint = new LinkedPoint(currentVIP);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            tempLinkedPoint.setPre(current);
                            current.setNext(tempLinkedPoint);
                            currentVIP.inComing = tempLinkedPoint;
                            currentVIP.inComingLine = ((GridIntersectPoint)(p)).getLine();
                            LinkedPoint temp = otherPoint.getPre();
                            //while (!(temp.getPoint() is IntersectPoint))
                            //{
                            //    temp = otherPoint.getPre();
                            //}
                            //LinkedPoint temp1 = otherPoint.getNext();
                            //while (!(temp1.getPoint() is IntersectPoint))
                            //{
                            //    temp1 = otherPoint.getNext();
                            //}
                            //((IntersectPoint)temp.getPoint()).inNext = otherPoint;
                            //((IntersectPoint)otherPoint.getPoint()).inNext = temp1;
                        }
                        else
                        {
                            tempLinkedPoint = new LinkedPoint(p);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            ((GridIntersectPoint)(p)).setLinkedPoint(tempLinkedPoint);
                            current.setNext(tempLinkedPoint);
                        }

                        if (endpoint != null)
                        {
                                
                            if(!poly.withinPolygon(current.getPoint(),endpoint)){
                                endpoint = null;
                            }
                            else {
                                // if this point is also a intersect point. 
                                if (endpoint.getLinkedPoint() != null)
                                {
                                    currentVIP = new VirtualIntersectPoint(endpoint.getX(), endpoint.getY());
                                    this.intersectPoints.Add(currentVIP);
                                    //currentVIP = endpoint.getLinkedPoint().getPoint() as VirtualIntersectPoint;
                                    specialPoint = new LinkedPoint(currentVIP);
                                    specialPoint.setPostPolygon(postPoly);
                                    otherPoint = endpoint.getLinkedPoint();
                                    //otherVIP = new VirtualIntersectPoint(otherPoint.getPoint().getX(), otherPoint.getPoint().getY());
                                    otherPoint.setPoint(currentVIP);
                                    //_configureIntersectPoint(current, current.getPre(), otherPoly, itsLine, otherLine, ref headIntersectPoint, ref currentIntersectPoint);
                                }
                                else
                                {
                                    specialPoint = new LinkedPoint(endpoint);
                                    specialPoint.setPostPolygon(postPoly);
                                    endpoint.setLinkedPoint(specialPoint);
                                }
                                _findVirtualIntersectPoint(current, specialPoint, postPoly);
                                _findVirtualIntersectPoint(specialPoint, tempLinkedPoint, postPoly);
                                if ((endpoint != null) && ((endpoint.getLinkedPoint() != specialPoint)))
                                {
                                    if (((IntersectPoint)(specialPoint.getNext().getPoint())).inComingLine.getPolygon() != poly)
                                    {
                                        ((IntersectPoint)(specialPoint.getPoint())).outGoing = specialPoint;
                                        ((IntersectPoint)(specialPoint.getPoint())).inComing = endpoint.getLinkedPoint();
                                        Line l1 = Line.generateDummyLine();
                                        l1.setPolygon(poly);
                                        Line l2 = Line.generateDummyLine();
                                        l2.setPolygon(endpoint.getLinkedPoint().getPostPolygon().getPolygon());
                                        ((IntersectPoint)(specialPoint.getPoint())).outGoingLine = l1;
                                        ((IntersectPoint)(specialPoint.getPoint())).inComingLine = l2;
                                    }
                                    else
                                    {
                                        ((IntersectPoint)(specialPoint.getPoint())).inComing = specialPoint;
                                        ((IntersectPoint)(specialPoint.getPoint())).outGoing = endpoint.getLinkedPoint();
                                        Line l1 = Line.generateDummyLine();
                                        l1.setPolygon(poly);
                                        Line l2 = Line.generateDummyLine();
                                        l2.setPolygon(endpoint.getLinkedPoint().getPostPolygon().getPolygon());
                                        ((IntersectPoint)(specialPoint.getPoint())).outGoingLine = l2;
                                        ((IntersectPoint)(specialPoint.getPoint())).inComingLine = l1;
                                    }
                                }
                            }
                        }
                        else
                        {
                            _findVirtualIntersectPoint(current, tempLinkedPoint, postPoly);
                        }
                        current = tempLinkedPoint;
                    } //end if
                    else
                    {
                        if (((GridIntersectPoint)(p)).getLinkedPoint() != null)
                        {
                             otherPoint = ((GridIntersectPoint)(p)).getLinkedPoint();
                             tempLinkedPoint = new LinkedPoint(otherPoint.getPoint());
                             tempLinkedPoint.setPostPolygon(postPoly);
                             ((VirtualIntersectPoint)(tempLinkedPoint.getPoint())).inComing = tempLinkedPoint;
                             Line tempLine = Line.generateDummyLine();
                             tempLine.setPolygon(poly);
                             ((VirtualIntersectPoint)(tempLinkedPoint.getPoint())).inComingLine = tempLine;
                             current.setNext(tempLinkedPoint);
                             tempLinkedPoint.setPre(current); 
                             current = tempLinkedPoint;
                             
                        }
                        else
                        {
                            tempLinkedPoint = new LinkedPoint(p);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            tempLinkedPoint.setPre(current);
                            current.setNext(tempLinkedPoint);
                            tempLinkedPoint.setPre(current);
                            current = tempLinkedPoint;
                            ((GridIntersectPoint)(p)).setLinkedPoint(tempLinkedPoint);
                        }
                        
                    }
                } //end if
            } // end for
            current.setNext(postPoly.getHead());
            postPoly.getHead().setPre(current);
            if ((this._onBorder(postPoly.getHead().getPoint())) && (this._onBorder(postPoly.getHead().getPre().getPoint())))
            {
                LinkedPoint lp2 = postPoly.getHead();
                Point p2 = lp2.getPoint();
                LinkedPoint lp1 = postPoly.getHead().getPre() ;
                Point p1 = lp1.getPoint();

                double x1 = p1.getX();
                double y1 = p1.getY();
                double x2 = p2.getX();
                double y2 = p2.getY();

                endpoint = null;
                if ((x1 == _xmin) && (y2 == _ymin))
                {
                    endpoint = this._leftBottomPoint;
                }
                else if ((y1 == _ymin) && (x2 == _xmax))
                {
                    endpoint = this._rightBottomPoint;
                }
                else if ((x1 == _xmax) && (y2 == _ymax))
                {
                    endpoint = this._rightTopPoint;
                }
                else if ((y1 == _ymax) && (x2 == _xmin))
                {
                    endpoint = this._leftTopPoint;
                }
                else if ((x1 == _xmin) && (y2 == _ymax))
                {
                    endpoint = this._leftTopPoint;
                }
                else if ((y1 == _ymax) && (x2 == _xmax))
                {
                    endpoint = this._rightTopPoint;
                }
                else if ((x1 == _xmax) && (y2 == _ymin))
                {
                    endpoint = this._rightBottomPoint;
                }
                else if ((y1 == _ymin) && (x2 == _xmin))
                {
                    endpoint = this._leftBottomPoint;
                }

                if (endpoint != null)
                {

                    if ( !poly.withinPolygon(p1,endpoint))
                    {
                    }
                    else
                    {
                        // if this point is also a intersect point. 
                        if (endpoint.getLinkedPoint() != null)
                        {
                            currentVIP = new VirtualIntersectPoint(endpoint.getX(), endpoint.getY());
                            this.intersectPoints.Add(currentVIP);
                            tempLinkedPoint = new LinkedPoint(currentVIP);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            otherPoint = endpoint.getLinkedPoint();
                            //otherVIP = new VirtualIntersectPoint(otherPoint.getPoint().getX(), otherPoint.getPoint().getY());
                            otherPoint.setPoint(currentVIP);
                            //_configureIntersectPoint(current, current.getPre(), otherPoly, itsLine, otherLine, ref headIntersectPoint, ref currentIntersectPoint);
                        }
                        else
                        {
                            tempLinkedPoint = new LinkedPoint(endpoint);
                            tempLinkedPoint.setPostPolygon(postPoly);
                            endpoint.setLinkedPoint(tempLinkedPoint);
                        }
                        //duplicate
                        _findVirtualIntersectPoint(lp1, tempLinkedPoint, postPoly);
                        _findVirtualIntersectPoint(tempLinkedPoint, lp2, postPoly);
                        if ((endpoint != null) && ((endpoint.getLinkedPoint() != tempLinkedPoint)))
                        {
                            if (((IntersectPoint)(tempLinkedPoint.getNext().getPoint())).inComingLine.getPolygon() != poly)
                            {
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).outGoing = tempLinkedPoint;
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).inComing = endpoint.getLinkedPoint();
                                Line l1 = Line.generateDummyLine();
                                l1.setPolygon(poly);
                                Line l2 = Line.generateDummyLine();
                                l2.setPolygon(endpoint.getLinkedPoint().getPostPolygon().getPolygon());
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).outGoingLine = l1;
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).inComingLine = l2;
                            }
                            else
                            {
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).inComing = tempLinkedPoint;
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).outGoing = endpoint.getLinkedPoint();
                                Line l1 = Line.generateDummyLine();
                                l1.setPolygon(poly);
                                Line l2 = Line.generateDummyLine();
                                l2.setPolygon(endpoint.getLinkedPoint().getPostPolygon().getPolygon());
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).outGoingLine = l2;
                                ((IntersectPoint)(tempLinkedPoint.getPoint())).inComingLine = l1;
                            }
                        }
                    }
                }
                else
                {
                    _findVirtualIntersectPoint(lp1, lp2, postPoly);
                }
              
            }
            //Console.WriteLine(postPoly.ToString());
            /*if the first point is intersect point*/
            if ((postPoly.getHead().getPoint() is IntersectPoint) && !(postPoly.getHead().getPoint() is VirtualIntersectPoint))
            {
                IntersectPoint intersectP = ((IntersectPoint)(postPoly.getHead().getPoint()));
                if (((IntersectPoint)intersectP).inComingLine.polygon == poly)
                {
                    otherLine = ((IntersectPoint)intersectP).outGoingLine;
                    otherPoly = otherLine.polygon;
                    itsLine = ((IntersectPoint)intersectP).inComingLine;
                }
                else
                {
                    otherLine = ((IntersectPoint)intersectP).inComingLine;
                    otherPoly = otherLine.polygon;
                    itsLine = ((IntersectPoint)intersectP).outGoingLine;
                }
                _configureIntersectPoint(current, current.getPre(), otherPoly, itsLine, otherLine, ref headIntersectPoint, ref currentIntersectPoint);
            }
            Console.WriteLine(postPoly.ToString());
            //Notice:we don't take into consideration the situation that when two polygons intersect, only one intersect point exists.
            if (headIntersectPoint != null)
            {
                ((IntersectPoint)(currentIntersectPoint.getPoint())).outNext = headIntersectPoint;
            }
            return postPoly;
        }

        /// <summary>
        /// determine if a point is within the range
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        private bool _withinRange(Point p)
        {
            if ((p.getX() <= _xmin) || (p.getX() >= _xmax) || (p.getY() <= _ymin) || (p.getY() >= _ymax))
            {
                return false;
            }
            return true;
        }

        private bool _onBorder(Point p){
            bool result=false;
             if (((p.getX()==_xmin) || (p.getX()== _xmax) )&&((p.getY()>=_ymin) && (p.getY()<=_ymax)))
            {
                result = true;
             }
             else if (((p.getY() == _ymin) || (p.getY() == _ymax)) && ((p.getX() >= _xmin) && (p.getX() <= _xmax)))
             {
                 result = true;
             }
             return result;
        }

        private void addVirtualIntersectPointAtX(ref LinkedPoint pre, ref LinkedPoint next, List<GridIntersectPoint> pointList, PostPolygon postPoly)
        {
            Point prePoint=pre.getPoint();
            Point nextPoint=next.getPoint();
            double min;
            double max;
            if(prePoint.getX()<nextPoint.getX())
            {
                min=prePoint.getX();
                max=nextPoint.getX();
                 for (int i = 0;i<=pointList.Count - 1; i++)
                {
                    if ((pointList[i].getX() > min) && (pointList[i].getX() < max))
                        {
                            addVirtualIntersectPointToList(ref pre,pointList[i],postPoly);
                        }
                }
            }
            else
            {
                max=prePoint.getX();
                min=nextPoint.getX();
                 for (int i = pointList.Count - 1; i >= 0; i--)
                {
                    if ((pointList[i].getX() > min) && (pointList[i].getX() < max))
                        {
                            addVirtualIntersectPointToList(ref pre, pointList[i], postPoly);
                        }
                }
            }
            pre.setNext(next);
            next.setPre(pre);

        }

        private void addVirtualIntersectPointAtY(ref LinkedPoint pre, ref LinkedPoint next, List<GridIntersectPoint> pointList, PostPolygon postPoly)
        {
            Point prePoint=pre.getPoint();
            Point nextPoint=next.getPoint();
            double min;
            double max;
            if(prePoint.getY()<nextPoint.getY())
            {
                min=prePoint.getY();
                max=nextPoint.getY();
                for (int i = 0;i<=pointList.Count - 1; i++)
                {
                    if ((pointList[i].getY() > min) && (pointList[i].getY() < max))
                        {
                            addVirtualIntersectPointToList(ref pre,pointList[i],postPoly);
                        }
                }

            }
            else
            {
                max=prePoint.getY();
                min=nextPoint.getY();
                 for (int i = pointList.Count - 1; i >= 0; i--)
                {
                    if ((pointList[i].getY() > min) && (pointList[i].getY() < max))
                        {
                            addVirtualIntersectPointToList(ref pre,pointList[i],postPoly);
                        }
                }
            }
            pre.setNext(next);
            next.setPre(pre);
        }

        private void addVirtualIntersectPointToList(ref LinkedPoint pre, GridIntersectPoint p, PostPolygon postPoly)
        {
            VirtualIntersectPoint currentVIP = null; 
            LinkedPoint currentPoint=null;
            currentVIP = new VirtualIntersectPoint(p.getX(), p.getY());
            this.intersectPoints.Add(currentVIP);
            currentPoint = new LinkedPoint(currentVIP);
            currentPoint.setPre(pre);
            currentPoint.setPostPolygon(postPoly);
            pre.setNext(currentPoint);
            pre = currentPoint;
            currentVIP.outGoing = currentPoint;
            Line dummyLine = Line.generateDummyLine();
            dummyLine.setPolygon(postPoly.getPolygon());
            currentVIP.outGoingLine = dummyLine;
            if (p.getLinkedPoint() != null)
            {
                LinkedPoint otherPoint = p.getLinkedPoint();
                otherPoint.setPoint(currentVIP);
                currentVIP.inComing = otherPoint;
                currentVIP.inComingLine = p.getLine();
            }
            else
            {
                p.setLinkedPoint(currentPoint);
            }
        }
        /// <summary>
        /// Some of the grid intersect points might also be intersect points.
        /// This method is to find these points.
        /// </summary>
        private void _findVirtualIntersectPoint(LinkedPoint pre, LinkedPoint next, PostPolygon postPoly)
        {
            double x1 = pre.getPoint().getX();
            double y1 = pre.getPoint().getY();
            double x2 = next.getPoint().getX();
            double y2 = next.getPoint().getY();
            if ((x1 == _xmin) && (x2 == _xmin))
            {
                addVirtualIntersectPointAtY(ref pre, ref next, this._leftGridIntersectPoints, postPoly);
            }
            else if ((x1 == _xmax) && (x2 == _xmax))
            {
                addVirtualIntersectPointAtY(ref pre, ref next, this._rightGridIntersectPoints, postPoly);
            }
            else if ((y1 == _ymin) && (y1 == _ymin))
            {
                addVirtualIntersectPointAtX(ref pre, ref next, this._bottomGridIntersectPoints, postPoly);
            }
            else if ((y1 == _ymax) && (y2 == _ymax))
            {
                addVirtualIntersectPointAtX(ref pre, ref next, this._topGridIntersectPoints, postPoly);
            }

        }
           
        #region
        // Intersect operation
        public List<PostPolygon>  intersect(List <IntersectPoint> points)
        {
            List<PostPolygon> postPolys = new List<PostPolygon>();
            for (int i = 0; i < points.Count(); i++)
            {
                if (points[i].inComing == null) continue;
                if (points[i].outGoing == null) continue;
                if ((points[i].inComing.getPostPolygon().getPolygon() is Hole) || (points[i].outGoing.getPostPolygon().getPolygon() is Hole))
                {
                    continue;
                }
                if (!points[i].ifVisited())
                {
                    IntersectPoint start = points[i];
                    start.hasVisited(true);
                    Polygon[] polys = new Polygon[2];
                    LinkedPoint next = start.inComing;
                    LinkedPoint temp = null;
                    PostPolygon postPoly = new PostPolygon(next);
                    postPolys.Add(postPoly);
                    next.setPostPolygon(postPoly);
                    polys[0] = start.inComingLine.getPolygon();
                    polys[1] = start.outGoingLine.getPolygon();
                    Console.WriteLine(start.ToString());
                    //Console.WriteLine(next.ToString());
                    do
                    {
                        next = next.getNext();
                        next.setPostPolygon(postPoly);
                        while (!(next.getPoint() is IntersectPoint))
                        {

                            Console.WriteLine(next.ToString());
                            selectIntersectPoint(next);
                            next = next.getNext();
                            next.setPostPolygon(postPoly);
                        }

                        if (next.getPoint() is IntersectPoint)
                        {
                            ((IntersectPoint)next.getPoint()).hasVisited(true);
                            if ((next.getPoint().Equals(this._leftBottomPoint)) || (next.getPoint().Equals(this._leftTopPoint)) || (next.getPoint().Equals(this._rightBottomPoint)) || (next.getPoint().Equals(this._rightTopPoint)))
                            {
                                Console.WriteLine(next.ToString());
                                //selectIntersectPoint(next);
                                temp = ((IntersectPoint)(next.getPoint())).transfer(next);
                                Console.WriteLine(temp.ToString());
                                temp.setPostPolygon(postPoly);
                                //selectIntersectPoint(temp);
                                this.selectIntersectPointForOriginalPoint(next, temp);
                                next.setNext(temp);
                                temp.setPre(next);
                                next = temp;
                            }
                            else
                            {
                                
                                temp = ((IntersectPoint)(next.getPoint())).transfer(next);
                                temp.setPostPolygon(postPoly);
                                Console.WriteLine(temp.ToString());
                                selectIntersectPoint(temp);
                                next.getPre().setNext(temp);
                                temp.setPre(next.getPre());
                                next = temp;
                            }
                                
                        }
                        
                    } while (next.getPoint() != start);
                    postPoly.getHead().setPre(next.getPre());
                    next.getPre().setNext(postPoly.getHead());
                    //removeIntersectPoint(next);
                }
            }
            return postPolys;
        }
        public void selectIntersectPointForOriginalPoint(LinkedPoint p1, LinkedPoint p2)
        {
            if (p1.getPoint().Equals(this._leftBottomPoint))
            {
                _bottomMergingIntersectPoints.Add(p1);
                _leftMergingIntersectPoints.Add(p2);
            }
            else if(p1.getPoint().Equals(this._leftTopPoint)){
                _leftMergingIntersectPoints.Add(p1);
                _topMergingIntersectPoints.Add(p2);
            }
            else if(p1.getPoint().Equals(this._rightTopPoint)){
                _topMergingIntersectPoints.Add(p1);
                _rightMergingIntersectPoints.Add(p2);
            }
            else if (p1.getPoint().Equals(this._rightBottomPoint))
            {
                _rightMergingIntersectPoints.Add(p1);
                _bottomMergingIntersectPoints.Add(p2);
            }
        }
        public void selectIntersectPoint(LinkedPoint next)
        {
            if ((next.getPoint() is GridIntersectPoint) ||(next.getPoint() is VirtualIntersectPoint))
            {
                if (next.getPoint().getX() == _xmin)
                {
                    _leftMergingIntersectPoints.Add(next);
                }
                if (next.getPoint().getX() == _xmax)
                {
                    _rightMergingIntersectPoints.Add(next);
                }
                if (next.getPoint().getY() == _ymin)
                {
                    _bottomMergingIntersectPoints.Add(next);
                }
                if (next.getPoint().getY() == _ymax)
                {
                    _topMergingIntersectPoints.Add(next);
                }
            }
        }
        public void removeIntersectPoint(LinkedPoint next)
        {
            if ((next.getPoint() is GridIntersectPoint) || (next.getPoint() is VirtualIntersectPoint))
            {
                if (next.getPoint().getX() == _xmin)
                {
                    _leftMergingIntersectPoints.Remove(next);
                }
                if (next.getPoint().getX() == _xmax)
                {
                    _rightMergingIntersectPoints.Remove(next);
                }
                if (next.getPoint().getY() == _ymin)
                {
                    _bottomMergingIntersectPoints.Remove(next);
                }
                if (next.getPoint().getY() == _ymax)
                {
                    _topMergingIntersectPoints.Remove(next);
                }
            }
        }
        //// Union operation
        //public void union()
        //{
        //    for (int i = 0; i < points.Count; i++)
        //    {
        //        if (!points[i].ifVisited())
        //        {
        //            IntersectPoint start = points[i];
        //            start.hasVisited(true);
        //            Console.WriteLine(start.ToString());
        //            List<Point> currentList = start.getOutLine();
        //            int currentPos = start.getOutPos();
        //            Point next = null;
        //            while (next != start)
        //            {

        //                //Console.WriteLine("pre-currentPos=" + currentPos);
        //                next = currentList[(++currentPos) % currentList.Count];
        //                //Console.WriteLine("currentPos="+currentPos);
        //                while (!(next is IntersectPoint))
        //                {
        //                    Console.WriteLine(next.ToString());
        //                    next = currentList[(++currentPos) % currentList.Count];

        //                }
        //                if (next is IntersectPoint)
        //                {
        //                    currentList = ((IntersectPoint)next).transfer(currentList);
        //                    currentPos = ((IntersectPoint)next).getCurrentPos();
        //                }
        //                Console.WriteLine(next.ToString());
        //                ((IntersectPoint)next).hasVisited(true);
        //            }
        //        }
        //    }
        //    Console.WriteLine("*************hole************");
        //    for (int i = 0; i < points.Count; i++)
        //    {
        //        if (!points[i].ifVisited())
        //        {
        //            IntersectPoint start = points[i];
        //            start.hasVisited(true);
        //            Console.WriteLine(start.ToString());
        //            List<Point> currentList = start.getInLine();
        //            int currentPos = start.getInPos();
        //            Point next = null;
        //            while (next != start)
        //            {

        //                //Console.WriteLine("pre-currentPos=" + currentPos);
        //                next = currentList[(--currentPos + currentList.Count) % currentList.Count];
        //                //Console.WriteLine("currentPos="+currentPos);
        //                while (!(next is IntersectPoint))
        //                {
        //                    Console.WriteLine(next.ToString());
        //                    next = currentList[(--currentPos + currentList.Count) % currentList.Count];

        //                }
        //                if (next is IntersectPoint)
        //                {
        //                    currentList = ((IntersectPoint)next).transfer(currentList);
        //                    currentPos = ((IntersectPoint)next).getCurrentPos();
        //                }
        //                Console.WriteLine(next.ToString());
        //                ((IntersectPoint)next).hasVisited(true);
        //            }
        //        }
        //    }
        //}

        #endregion
    }
}
